﻿// ******************************************************************************************************
// <copyright file="QuadTree.cs" company="Caroso.inc">
//     Copyright (c) Carlos Osorio All rights reserved.
// </copyright>
// ******************************************************************************************************
// The contents of this file are subject to the Mozilla Public License Version 1.1 (the "License"); 
// you may not use this file except in compliance with the License. You may obtain a copy of the License at 
// http:// www.mozilla.org/MPL/ 
// Software distributed under the License is distributed on an "AS IS" basis, WITHOUT WARRANTY OF 
// ANY KIND, either express or implied. See the License for the specificlanguage governing rights and 
// limitations under the License. 
// 
// The Original Code is this .mapWindow 
// 
// The Initial Developer of this version of the Original Code is Carlos Osorio carosocali@gmail.com
// 
// Contributor(s): (Open source contributors should list themselves and their modifications here). 
// Change Log: 
// Date           Changed By      Notes
// 6 jun 2011    Carlos Osorio   Inital upload t
// ******************************************************************************************************
namespace Velsto
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    /// <summary>
    /// Class to generate a spatial index
    /// </summary>
    public class QuadTree
    {
        /// <summary>
        ///  Node use in the index
        /// </summary>
        private Node root;
        
        /// <summary>
        /// Store list point searched
        /// </summary>
        private ArrayList data = new ArrayList();

        /// <summary>
        /// Insert a new node in the index
        /// </summary>
        /// <param name="x">X position of the node</param>
        /// <param name="y">Y position of the node</param>
        /// <param name="value">value associated with the node</param>
        public void Insert(
            double x, double y, int value) 
        {
            this.root = this.Insert(this.root, x, y, value);
        }

        /// <summary>
        /// This method requests the nodes in a rectangle
        /// </summary>
        /// <param name="rect">Rectange in which the nodes are searched</param>
        public void Query2D(
            Interval2D rect)
        {
            this.Query2D(this.root, rect);
        }

        /// <summary>
        /// Clean the data of a Query
        /// </summary>
        public void Clean()
        {
            this.data.Clear();
        }

        /// <summary>
        /// Obtain the data of a Query
        /// </summary>
        /// <returns>An arrayList with the id of point searched</returns>
        public ArrayList GetData()
        {
            return this.data;
        }

        /// <summary>
        /// Evaluates to double values if K1 is less of K2
        /// </summary>
        /// <param name="k1">First value to be compared</param>
        /// <param name="k2">Second value to be compared</param>
        /// <returns>True is K1 less than K2</returns>
        private bool Less(
            double k1, double k2) 
        { 
            return k1.CompareTo(k2) < 0; 
        }
        
        /// <summary>
        /// Evaluates to double values if K1 is equal to K2
        /// </summary>
        /// <param name="k1">First value to be compared</param>
        /// <param name="k2">Second value to be compared</param>
        /// <returns>True if K1 is equal to K2</returns>
        private bool Eq(
            double k1, double k2) 
        { 
            return k1.CompareTo(k2) == 0; 
        }

        /// <summary>
        /// Insert a new Node return it
        /// </summary>
        /// <param name="h">Root Node index</param>
        /// <param name="x">X position of the node</param>
        /// <param name="y">Y position of the node</param>
        /// <param name="value">value associated with the node</param>
        /// <returns>Returns the node in the rigth position </returns>
        private Node Insert(
            Node h, double x, double y, int value)
        {
            if (h == null)
            {
                return new Node(x, y, value);
            }
            else if (this.Less(x, h.X) && this.Less(y, h.Y))
            {
                h.SW = this.Insert(h.SW, x, y, value);
            }
            else if (this.Less(x, h.X) && !this.Less(y, h.Y))
            {
                h.NW = this.Insert(h.NW, x, y, value);
            }
            else if (!this.Less(x, h.X) && this.Less(y, h.Y))
            {
                h.SE = this.Insert(h.SE, x, y, value);
            }
            else if (!this.Less(x, h.X) && !this.Less(y, h.Y))
            {
                h.NE = this.Insert(h.NE, x, y, value);
            }

            return h;
        }

        /// <summary>
        /// This method requests the nodes in a rectangle in a node level
        /// </summary>
        /// <param name="h">The root node to be searched</param>
        /// <param name="rect">Rectange in which the nodes are searched</param>
        private void Query2D(
            Node h, Interval2D rect)
        {
            if (h == null)
            {
                return;
            }

            double xmin = rect.IntervalX.Low;
            double ymin = rect.IntervalY.Low;
            double xmax = rect.IntervalX.High;
            double ymax = rect.IntervalY.High;
            if (rect.Contains(h.X, h.Y))
            {
                this.data.Add(h.Value);
            }

            if (this.Less(xmin, h.X) && this.Less(ymin, h.Y))
            {
                this.Query2D(h.SW, rect);
            }

            if (this.Less(xmin, h.X) && !this.Less(ymax, h.Y))
            {
                this.Query2D(h.NW, rect);
            }

            if (!this.Less(xmax, h.X) && this.Less(ymin, h.Y))
            {
                this.Query2D(h.SE, rect);
            }

            if (!this.Less(xmax, h.X) && !this.Less(ymax, h.Y))
            {
                this.Query2D(h.NE, rect);
            }
        }

        /// <summary>
        /// This class creates a Node
        /// </summary>
        private class Node
        {
            /// <summary>
            ///  Store the x, y position
            /// </summary>
            private double x, y;

            /// <summary>
            /// Nodes in each region
            /// </summary>
            private Node nw, ne, se, sw;

            /// <summary>
            /// Values stored in the node
            /// </summary>
            private int value;

            /// <summary>
            /// Initializes a new instance of the Node class
            /// </summary>
            /// <param name="x">X position of the node</param>
            /// <param name="y">Y position of the node</param>
            /// <param name="value">value associated with the node</param>
            public Node(
                double x, double y, int value)
            {
                this.x = x;
                this.y = y;
                this.value = value;
            }

            /// <summary>
            /// Gets or sets of the X value
            /// </summary>
            public double X
            {
                get { return this.x; }
                set { this.x = value; }
            }
            
            /// <summary>
            /// Gets or sets of the Y value
            /// </summary>
            public double Y
            {
                get { return this.y; }
                set { this.y = value; }
            }

            /// <summary>
            /// Gets or sets of the NW node
            /// </summary>
            public Node NW
            {
                get { return this.nw; }
                set { this.nw = value; }
            }

            /// <summary>
            /// Gets or sets of the NE node
            /// </summary>
            public Node NE
            {
                get { return this.ne; }
                set { this.ne = value; }
            }

            /// <summary>
            /// Gets or sets of the SE node
            /// </summary>
            public Node SE
            {
                get { return this.se; }
                set { this.se = value; }
            }

            /// <summary>
            /// Gets or sets of the SW node
            /// </summary>
            public Node SW
            {
                get { return this.sw; }
                set { this.sw = value; }
            }

            /// <summary>
            ///  Gets or sets of the value
            /// </summary>
            public int Value
            {
                get { return this.value; }
                set { this.value = value; }
            }
        }
    }
}
